from sklearn import datasets
import numpy as np
import random
import matplotlib.pyplot as plt
import time
import copy #便于判断集合是否为一个聚类时合并


"""
1.针对二维坐标x y的情况 
在使用原来的csv文件提供的数据集时，dbscan对于内部较为集中的数据可以很好地分成一类
但是如果minPts的值较大，外围数据可能全部都被归为噪点
如果minPts较小，外围数据可能会被分成很多个类别
也即dbscan方法比较依赖于参数的选择

所以在展示的方法中针对二维坐标我们使用了sklearn中的makecircles进行重构

2.在完成了kmeans的第二问之后，发现dbscan同样也可以采用坐标压缩的方法
  因此最终在呈现时我们采用的是这种方法，sklearn重构数据的方法以注释的形式给出
"""
def distance_calc(a1,a2):
    return np.sum(np.square(a1-a2))

def find_neighbor(j, x, radius):
    '''
    :return: 目标点radius邻域内的点的个数
    '''
    N = []
    for i in range(x.shape[0]):
        temp = np.sqrt(np.sum(np.square(x[j] - x[i])))  # 计算欧式距离
        if temp <= radius:
            N.append(i)
    return set(N)#返回一个集合，方便做元素的添加和删减


def DBSCAN(X, radius, minPts):
    k = -1
    neighbor_list = []  # 用来保存每个数据的邻域
    center_points = []  # 核心对象集合
    gama = set([x for x in range(len(X))])  # 初始时将所有点标记为未访问
    cluster = [-1 for _ in range(len(X))]  # 聚类

    for i in range(len(X)):
        neighbor_list.append(find_neighbor(i, X, radius))
        if len(neighbor_list[-1]) >= minPts:
            center_points.append(i)  # 将样本加入核心对象集合
    center_points = set(center_points)  # 转化为集合便于操作

    while len(center_points) > 0:#判断重复点，将有相同点的核心对象归为一个聚类
        gama_old = copy.deepcopy(gama)#记录当前为访问样本集合
        j = random.choice(list(center_points))  # 随机选取一个核心对象
        k = k + 1
        Q = list()
        Q.append(j)
        gama.remove(j)

        while len(Q) > 0:
            q = Q[0]
            Q.remove(q)#取出队列中的首个样本
            #判断这个样本是否为核心对象
            if len(neighbor_list[q]) >= minPts:
                delta = neighbor_list[q] & gama
                deltalist = list(delta)
                for i in range(len(delta)):
                    Q.append(deltalist[i])
                    gama = gama - delta
        Ck = gama_old - gama
        Cklist = list(Ck)
        for i in range(len(Ck)):
            cluster[Cklist[i]] = k
        center_points = center_points - Ck
    return cluster

import csv
#load data from csv file
data1= np.loadtxt(open('dataset_circles.csv'),delimiter=",",skiprows=0)
data=data1[:,:2]
n,m=np.shape(data)#总共有n个数据点
n=int(n)
m=int(m)
X = data #X表示的是原始的坐标
distance=np.zeros((len(data),2))#distance表示的是压缩到一个轴的坐标
origin=np.array([0,0])
for i in range(len(data)):
    distance[i][0]=distance_calc(data[i],origin)

#因为dbscan针对distance的分类都是到原点距离，值都较大
#因此判断核心对象的半径可以取值较大
eps = 100
minPts =15
begin = time.time()
C = DBSCAN(distance, eps, minPts)
end = time.time()

#plot the result
plt.figure()
plt.scatter(X[:, 0], X[:, 1], c=C)
plt.title("Cluster Result")
plt.show()

#load data from sklearn.datasets,make_circles
#X1, y1 = datasets.make_circles(n_samples=800, factor=.6, noise=.02)
#X=X1
#eps = 0.08
#minPts =7
#set dbscan parameters
#begin = time.time()
#C = DBSCAN(X, eps, minPts)
#end = time.time()
##plot the result
#plt.figure()
#plt.scatter(X[:, 0], X[:, 1], c=C)
#plt.title("Cluster Result")
#plt.show()